//给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。 
//
// 
//
// 示例 1： 
//
// 
//输入：nums = [1,5,11,5]
//输出：true
//解释：数组可以分割成 [1, 5, 5] 和 [11] 。 
//
// 示例 2： 
//
// 
//输入：nums = [1,2,3,5]
//输出：false
//解释：数组不能分割成两个元素和相等的子集。
// 
//
// 
//
// 提示： 
//
// 
// 1 <= nums.length <= 200 
// 1 <= nums[i] <= 100 
// 
//
// Related Topics 数组 动态规划 👍 1973 👎 0


package com.tyrone.leetcode.editor.cn;

import java.util.LinkedList;
import java.util.Queue;

public class PartitionEqualSubsetSum {
    public static void main(String[] args) {
        Solution solution = new PartitionEqualSubsetSum().new Solution();
        System.out.println(solution.canPartition(new int[]{1,5,11,5}));
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        /**
         * 最直观的想法是 计算总和然后 求他的一半
         * 然后在数字里面不断枚举组合,判断有没有等于一半的
         * 只要当组合数大于一半都是不行的
         * 一开始想通过回溯 但是事件复杂太高了
         * <p>
         * 看了题解用的是dp 还是背包问题
         *
         * @param nums
         * @return
         */
        public boolean canPartition(int[] nums) {
            int sum = 0;
            int n = nums.length;
            boolean[] used = new boolean[n];
            for (int i = 0; i < n; i++) {
                sum += nums[i];
            }
            if (sum % 2 != 0) return false;
            int target = sum >> 1;

            /**
             * dp[i][j] 表示 从nums[i] 以前选物品，她的价值能否等于j
             * 如果是dp[imax][jmax] 是true 就说明 在imax之前能够价值能够等于target
             *
             * 官方的题解是这么解释的：
             * dp[i][j] 表示表示从数组的 [0-i] 下标范围内选取若干个正整数（可以是 0 个）
             * 是否存在一种选取方案使得被选取的正整数的和等于 j。初始时，dp中的全部元素都是 false
             *。
             *
             *
             * 状态转移方程
             * 不选择 nums[i]，如果在 [0, i - 1] 这个子区间内已经有一部分元素，使得它们的和为 j ，那么 dp[i][j] = true；
             * 选择 nums[i]，如果在 [0, i - 1] 这个子区间内就得找到一部分元素，使得它们的和为 j - nums[i]。
             */
            boolean[][] dp = new boolean[n][target + 1];
            //dp【0】表示只选择第一个元素 那么这个时候只有 dp[0][nums[0]] = true
            if (nums[0] <= target) {
                dp[0][nums[0]] = true;
            }

            /**
             * 一直有个疑惑？ 导致在哪里做的判断 判断当前累加 和 target相等？
             * nums[i] == j时   dp[i][j] = true; 说明 只选择一个的时候总和
             * 其余的总和判断是根据
             * dp[i][j] = dp[i - 1][j] || dp[i - 1][j - nums[i]];
             * 来填充的。
             * 具体的累加 和 target 的判断结果直接存储到 [target]列中了
             */
            for (int i = 1; i < n; i++) {
                for (int j = 0; j < target + 1; j++) {
                    dp[i][j] = dp[i - 1][j];
                    if (nums[i] == j) {
                        dp[i][j] = true;
                        continue;
                    }
                    if (nums[i] < j) {
                        //选择下标i的元素和不选择的下标i的元素
                        dp[i][j] = dp[i - 1][j] || dp[i - 1][j - nums[i]];
                    }
                }
            }
            return dp[n-1][target];
        }


    }
//leetcode submit region end(Prohibit modification and deletion)

}